package com.example.algorithm;

/**
 * 爬到楼顶的方法数
 *
 * @author huahua
 * @DATE 2025/3/14
 **/
public class ClimbStaris {
    public static void main(String[] args) {
        // 比如3层，可以是1+1+1或者1+2或者2+1，总共3中方法
        System.out.println(getClimbStairs(3));
    }

    public static int getClimbStairs(int n) {
        // 采用动态规划的思想，每次可以爬1级或2级台阶，求解爬到楼顶的方法数
        if(n == 1){
            return 1;
        }
        // 数组dp用于存储到达每个台阶的方法数
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            // 使用动态规划思想，通过循环从第 2 个台阶开始计算，dp[i] = dp[i-1] + dp[i-2]，
            // 表示到达当前台阶的方法数等于到达前一级和前两级台阶方法数之和。
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

}
